1. Field of the Invention
The present invention relates to a terminal suitable for use in an asynchronous transfer mode network and a variable-length packet network, and particularly to a technique for allocating shaping bandwidths between respective users.
2. Description of the Related Art
An asynchronous transfer mode technique has been widely known as a communication technique which is capable of supporting various types of traffics such as speech, images, data, etc. with efficiency using fixed-length packets called xe2x80x9ccellsxe2x80x9d and suitable for multimedia communications. The asynchronous transfer mode technique has been described in, for example, xe2x80x9cThe ATM Forum TM4.0xe2x80x9d (Prior Art 1).
FIG. 2 show a general network comprised of a plurality of terminals and switches. In the case of an asynchronous transfer mode network, however, cells are transferred through virtual paths called xe2x80x9cconnectionsxe2x80x9d as described in xe2x80x9c2. ATM Service Architecture (p.4)xe2x80x9d of the Prior Art 1. When each cell is transferred from one terminal 10 (hereinafter called xe2x80x9csource terminal or source end systemxe2x80x9d) to another terminal 20 (hereinafter called xe2x80x9cdestination terminal or destination end systemxe2x80x9d) in FIG. 2, virtual paths (connections) are established between the source terminal 10, switches 30, 31, 32 and destination terminal 20. The cells are transferred over the connections which connect between both the terminals 10 and 20. As the establishment of the connections, there are two cases: one required by a source terminal and another required by a terminal 15 for network management.
In the multimedia communications, a burst traffic for communicating data and a real-time traffic for communicating signals, such as speech, picture or the like, are simultaneously transferred through different connections lying within the same line. When connections incoming from a plurality of input lines merge with each other at one of output ports of a switch, it is required to carry out cell transmission control (i.e., traffic control) on individual connections. As to the real-time traffic, each bandwidth for use in the transfer of signals, such as speech, picture or the like, can be estimated in advance. In order to reserve a necessary bandwidth (hereinafter called xe2x80x9cshaping bandwidthxe2x80x9d) within a cell communication path before the commencement of cell transmission and perform low-delay transmission within such a reserved bandwidth, real-time traffic cells are transmitted preferentially to burst traffic cells forwarding to the same output port.
A cell sending apparatus needs to transmit output cells in the secured shaping bandwidth. For this purpose, it is necessary to provide the function of sending cells in a reserved bandwidth for each connection. The cell sending function in this reserved bandwidth will hereinafter be called xe2x80x9cshapingxe2x80x9d.
A shaping apparatus or a shaper has been disclosed in, for example, Japanese Unexamined Patent Publication No. Hei 6-315034, xe2x80x9cCell Flow Control Device and ATM Communication Networkxe2x80x9d (Prior Art 2). The xe2x80x9cCell Flow Control Devicexe2x80x9d in the Prior Art 2 is the same meaning as the shaper. In the Prior Art 2, the shaping apparatus is constructed as shown in FIG. 3. The shaper 7 comprises a policing part 2 for determining whether an incoming cell interval falls within a prescribed allowable value, a cell sending time arithmetic part 3 for calculating the output time of each cell, a memory 4 for temporarily storing each cell therein, a write control circuit 5 for writing cells into the memory 4, and a read control circuit 6 for reading out the stored cells from the memory 4. Even when the incoming cells are received in a bandwidth higher than the sending bandwidth, since these cells are temporarily stored in the memory 4, these cells can be transmitted maintaining the contracted shaping bandwidth.
The shaping is also required to the burst traffic cells other than the real-time traffic cells. In the case of the burst traffic data communication, the shaping bandwidth cannot be estimated in advance. However, since reducing a transmission delay is not so important in the burst traffic data, the source terminal may start cell sending without ensuring the shaping bandwidth. Even if traffics are concentrated on one of nodes or a network congestion has occurred on one of output lines, high availability of the network may be realized by temporarily storing incoming cells in buffers provided within the network. However, if the amount of cells flow into the network in excess of the ability of the network to process the cells, the cells overflowed from the buffer must be discarded in the course of their transmission.
In the Prior Art 1, two traffic classes are defined for the data communication traffic from the viewpoint of such cell discard.
One of them is an ABR (Available Bit Rate) class for performing dynamic control on the shaping bandwidth in the network. For this class, a congestion notification cell circulated into the network regularly in order to monitor the state of the congestion of the network (hereinafter called xe2x80x9ccongestion statusxe2x80x9d) is utilized to decrease the amount of flow of cells into the network upon congestion and increase the amount of flow of cells upon non-congestion, so that cell transfer is smoothly performed without causing cell discard. A model for the ABR class has been described in, for example, xe2x80x9c5.10 ABR Flow Control (p.44)xe2x80x9d in the Prior Art 1. Another class is a UBR (Unspecified Bit Rate) class. In this class, emphasis is laid on effective use of available bandwidth. Even if a network is placed in a congestion status and brought to a state of causing cell discard, no limitation is imposed on the shaping bandwidth.
In the Prior Art 1, as shown in the model for ABR control in FIG. 4 (see FIG. 2-1 in the Prior Art 1), one of switches 30 through 33 or destination terminal 20 having detected the congestion of the network sets a congestion notification bit in a congestion notification cell circulated into each connection to xe2x80x9c1xe2x80x9d. When the source terminal 10 receives the congestion notification cell whose congestion notification bit is set to xe2x80x9c1xe2x80x9d, it determines that the network is congested, and thereby decreases the transmission bandwidth to prevent the flow of excessive cells into the network. If a congestion notification cell whose congestion notification bit is not set to xe2x80x9c1xe2x80x9d, is received, the source terminal 10 determines that the network is not congested, and hence increases the transmission bandwidth to up the availability of the network.
Even when the congestion notification cell whose congestion notification bit is set to xe2x80x9c1xe2x80x9d, is received at this time, it is unnecessary to reduce the cell transmission bandwidth to a bandwidth which falls below MCR (Minimum Cell Rate) contracted upon connection setting. The dynamic control on the transmission bandwidth can be performed from the network side by executing feedback control using such a congestion notification cell.
FIG. 4 shows only the flow of data cells in one direction from the source terminal 10 to the destination terminal 20 for simplification. Since, however, an actual terminal apparatus performs both operation for the source terminal and operation for the destination terminal, the flow of the data cells from the destination terminal 20 to the source terminal 10 also exists. The above-described one-direction communication model will be explained unless otherwise specified.
In the Prior Art 1, the congestion notification cell is called xe2x80x9cRM cell (Resource Management Cell)xe2x80x9d. One transferred from the source terminal to the destination terminal is referred to as xe2x80x9cforward RM cellxe2x80x9d, and one transferred from the destination terminal to the source terminal is called xe2x80x9cbackward RM cellxe2x80x9d. In the following description, the forward RM cell and the backward RM cell are referred to as FRM cell and BRM cell in accordance with the above designations. A distinction between the FRM cell and the BRM cell is made according to a bit (DIR bit) indicative of a transfer direction, lying in the RM cell. Namely, a cell with DIR=0 is determined as the FRM cell, whereas a cell with DIR=1 is determined as the BRM cell.
According to the description in xe2x80x9c5.10 ABR Flow Controlxe2x80x9d of the Prior Art 1, the control on a shaping bandwidth based on congestion notification information for the RM cell is intended for the case in which a bandwidth calculating source terminal is defined as a starting point of a single connection. No mention is made of the case in which a source terminal is defined as a starting point for a plurality of connections. When a source terminal serves as a starting point for the plurality of connections, it is important to equally allocate the bandwidth of a communication path to respective connections or to preferentially assign the bandwidth to important connections regardless of whether the feedback control using the RM cell is being performed (ABR class) or not (UBR class).
The fairness of bandwidth allocation has been described in, for example, xe2x80x9cInformative Appendix I.3 Example Fairness Criteria (p.82)xe2x80x9d of the Prior Art 1. In the xe2x80x9cInformative Appendix I.3 Example Fairness Criteriaxe2x80x9d of the Prior Art 1, xe2x80x9cMax-Min, MCR plus equal sharexe2x80x9d for equally dividing the bandwidth by all connections, and xe2x80x9cWeight allocationxe2x80x9d for performing weighting every connections, etc. are defined as fairness criteria.
For the ABR class , an ERICA method is known as one means for implementing the equal share of the bandwidths for the communication path. The ERICA method has been described in, for example, xe2x80x9cInformative Appendix I.5 Example Switch Mechanism (p.85)xe2x80x9d of the Prior Art 1. According to the ERICA method, a switch or a destination terminal within a network notifies to a source terminal such a value as a shaping allowed bandwidth that is obtained by equally dividing the bandwidth of each communication path inputted to the switch or the destination terminal. Using the ERICA method, it possible to perform equal division of the bandwidths for the communication path. xe2x80x9cPacket Scheduling Devicexe2x80x9d described in Japanese Unexamined Patent Publication No. Hei 9-83547 is known as a Prior Art 3. According to the Prior Art 3, a shaping apparatus, which supports a plurality of connections for UBR class, has a plurality of first queues prepared one for each connection and a second queue for storing elements indicative of access order of the first queues. Transmission cells are read out from the first queues according to the indication of an element read out from the second queue. The second queue can store a limited number of elements equal to the number corresponding to the weight of a transmission ratio between the respective connections. The Prior Art 3 can control the rate of transmission cells of a plurality of connections for UBR class.
Further, an ABR control technique using VS/VD (Virtual Source/Virtual Destination) for a long distance connection extending from a source terminal to a destination terminal has been disclosed in xe2x80x9c115.10.7 Virtual Source and Virtual Destinationxe2x80x9d of the Prior Art 1.
Since the long-distance connection needs time until congestion notification information is notified to the source terminal and the shaping bandwidth is reduced in controllability, a path defined between a source terminal 11 and a destination terminal 21 is divided by a VS/VD 60 provided on its way as shown in FIG. 5 (FIG. 5-5 in the Prior Art 1) in order to prevent the congestion notification from being delayed due to the long distance. The VS/VD allows each data cell to pass therethrough as it is. With respect to the transmission and reception of RM cells, the VS 40 performs the same operation as that of the source terminal 11 and the VD 50 performs the same operation as that of the destination terminal 21.
Three types of embodiments shown below are known as configurations for VS/VD. Namely, they area configuration for the node 60 independent of others as shown in FIG. 5, a configuration in which VS/VD is placed in a line interface unit of a switch 35 as shown in FIG. 6, and a configuration in which VS/VD is provided as a trunk attached to a switch 36 as shown in FIG. 7.
As to VS/VD, for example, xe2x80x9cATM WAN architecture for implementation of multi protocol, part 1xe2x80x9d is described in The Institute of Electronics, Information and Communication Engineers Technical Report SSE95-186 (1996-03) (Prior Art 4). The Prior Art 4 has proposed a system for applying VD/VD to an actual network and introducing an ABR class at low cost and shows a necessary buffer amount or the like.
Further, Japanese Unexamined Patent Publication No. 10-215253 (Prior Art 5) discloses to multiplex a plurality of VPC lying on the same path and a shared VPC passing through the same path as for the plurality of VPC in order to supplement the excess and deficiency of bandwidths for VPC by the bandwidth held by the shared VPC, wherein the plurality of VPC are switched by a plurality of ATM nodes located between a starting point and an end point and the shared VPC has a bandwidth to be shared by the plurality of VPC. However, the allocation of shaping bandwidths at a source terminal has not been discussed in the Prior Art 5.
In the following description, the source terminal and VS of VS/VD are both called xe2x80x9ccell source devicexe2x80x9d. The ERICA method of the Prior Art 1 is a method for allocating bandwidths for a communication path connected to the switch or destination terminal. A bandwidth notified to the cell source device does not take into consideration each bandwidth for the communication path connected to the cell source device. In the cell source device which supports a plurality of connections, the total bandwidth calculated and notified by each individual connection ERIC methods might exceed the actual bandwidth of the communication path connected to the cell source device. In this case, cell source device cannot transmit the cells in the notified bandwidth. Further, the cells are not always transmitted to each connection in a bandwidth greater than the above-described MCR (Minimum Cell Rate). It is thus necessary for the cell source device to allocate the bandwidth of the communication path connected to the cell source device to each connection.
According to the Prior Art 3, the cell source device assigns weights to the respective connections and makes it a rule to transmit the cell if a vacant bandwidth exists in an outgoing communication path. Accordingly, the cell source device performs only operation for the UBR class and is not applicable to the ABR class for sending cells while maintaining the specified shaping bandwidth. Further, the cell source device cannot ensure the transmission of cells to each connection in a bandwidth greater than MCR either.
A first object of the present invention is to propose a shaping bandwidth control system suitable for use in a cell source device supporting a plurality of connections, which secures the transmission of cells to each connection in a bandwidth greater than MCR and allocates bandwidths other than MCR to the respective connections at a ratio corresponding to the priorities of the respective connections.
In the ABR class, the cell source device must send cells in a bandwidth less than the notified value when the cell source device is notified through the RM cell that the network is congested. The cell source device allocates the bandwidth of a communication path to respective connection on the communication path so that the total of the bandwidths assigned to these connections equals to the bandwidth of the communication path. In this situation, if the cell source device is notified from the network of a bandwidth value for a specified connection which is smaller than a bandwidth originally assigned to the connection, the sum of shaping bandwidths for all the connections becomes smaller than the bandwidth of the communication path connected to the cell source device. Namely, a vacant bandwidth occurs in the bandwidth of the communication path, so that the bandwidth for the communication path cannot be effectively utilized. It is desirable for each connection to release the excessively-assigned bandwidth (bandwidth corresponding to the difference between a bandwidth originally assigned by bandwidth allocation and an actually cell-sending bandwidth) when its shaping bandwidth is reduced by the congestion notification, so that the bandwidth is re-allocated to other connections.
A second object of the present invention is to propose a shaping bandwidth control system suitable for use in a cell source device supporting a plurality of connections, wherein a connection to which a value smaller than a shaping bandwidth assigned by a bandwidth allocation function is notified by a congestion notification sent from a network, releases an excessive bandwidth corresponding to the difference between a bandwidth assigned to the connection and an actual shaping bandwidth of the connection, whereby high availability of the network can be achieved as a whole by re-allocating the released bandwidth to the other connections.
While the increase or decrease in shaping bandwidth based on the congestion notification information at the source terminal has been described in the xe2x80x9c15.10 ABR Flow Control (p.44) of the Prior Art 1, the bandwidth allocation for the source terminal has not been described.
A third object of the present invention is to provide a configuration of a source terminal provided with circuits for implementing the shaping bandwidth control described in the first and second objects.
While the concept of VS/VD and the conditions to be met are simply described in the xe2x80x9c5.10.7 Virtual Source and Virtual Destinationxe2x80x9d of the Prior Art 1, no mention is made of a method of specifically configuring VS/VD. Further, only the VS/VD utilizing method is described in the Prior Art 3 and hence this is not related to the configuration of VS/VD.
A fourth object of the present invention is to provide a configuration of VS/VD provided with circuits for implementing the shaping bandwidth control described in the first and second objects.
Further, the shaping and bandwidth allocation is a technique important not only for the ATM cell but also for a general variable-length packet transfer.
A fifth object of the present invention is to provide a shaping bandwidth control system capable of achieving high availability of a network as a whole for a variable-length packet such as an IP (Internet Protocol) packet.
In order to achieve the above objects, there is provided a source terminal according to the present invention, for transferring data cells and congestion notification cells to a destination terminal through a connection within an asynchronous transfer mode network including at least one transit switching system, comprising: shaping bandwidth control means for increasing or decreasing each of shaping bandwidths, based on congestion notification information written into a congestion notification cell sent back from the destination terminal or the transit switching system to the source terminal in a congested status, the shaping bandwidth control means including, memory means for storing therein priority information indicative of priorities for bandwidth allocation at cell transfers for each connection; and shaping bandwidth calculating means for calculating each cell shaping bandwidth, based on the priority information when a plurality of connections are simultaneously placed in a cell transfer state, whereby the shaping bandwidths are allocated between all the connections placed in the cell transfer state.
The shaping bandwidth control means multiplies, for example, a ratio obtained by dividing the priority information for the respective connections by the sum of the priority information for all the connections each placed in the cell transfer state, of connections established over the same line as that for the connections by the shaping bandwidth for the line, thereby calculating a cell shaping bandwidth proportional to the priority information for each connection.
According to one embodiment of the present invention, the shaping bandwidth control means has memory means for storing therein information of minimum secured bandwidth value for each connection, and the shaping bandwidth calculating means includes means for multiplying a ratio obtained by dividing the priority information for the respective connections by the sum of the priority information for all the connections each placed in the cell transfer state, of connections established over the same line as that for the connections by a bandwidth obtained by subtracting minimum secured bandwidths for all the connections to be sent to the line from the shaping bandwidth for the line, and for adding the minimum secured bandwidth value to the obtained result, thereby calculating the cell shaping bandwidth for each connection, whereby the shaping bandwidth control means ensures the minimum secured bandwidth for each connection and allocates the cell shaping bandwidths to the respective connections in proportion to the priority information for the respective connections as bandwidths freely allocable with the respective connections.
There is also provided a source terminal according to the present invention, for transferring data cells and congestion notification cells to a destination terminal through a connection preset within an asynchronous transfer mode network including at least one transit switching system, comprising: shaping bandwidth control means for increasing or decreasing each of shaping bandwidths, based on congestion notification information written into a congestion notification cell sent back from the destination terminal or the transit switching system to the source terminal in a congested status, the shaping bandwidth control means including, memory means for storing therein priority information indicative of priorities for bandwidth allocation at cell transfers for each connection; and means for multiplying a ratio obtained by dividing a minimum secured bandwidth for each connection by the sum of minimum secured bandwidths for all connections each placed in a cell transfer state, of connections established over the same line as the connections by a shaping bandwidth for the line thereby allocating cell shaping bandwidths to the respective connections in proportion to a shaping bandwidth desired to be ensured as the minimum.
There is further provided a source terminal according to the present invention, for transferring data cells and congestion notification cells to a destination terminal through a connection preset within an asynchronous transfer mode network including at least one transit switching system, comprising: shaping bandwidth control means for decreasing a cell shaping bandwidth when a congestion notification bit is set to a congestion notification cell sent back from the destination terminal or the transit switching system to the source terminal, and increasing the cell shaping bandwidth when the congestion notification bit is not set thereto, the shaping bandwidth control means including, means for dividing each cell shaping bandwidth for one line by the number of connections each established over the line and placed in a cell transfer state when a plurality of the connections are simultaneously placed in the cell transfer state, thereby uniformly allocating the cell shaping bandwidth to each connection.
According to one embodiment of the present invention, the shaping bandwidth control means includes memory means for storing therein information of minimum secured bandwidth value for each connection, and means for dividing a bandwidth obtained by subtracting the sum of minimum secured bandwidths for all the connections, sent to one line from a shaping bandwidth for the line by the number of the connections each established over the line and placed in the cell transfer state, and further adding the minimum secured bandwidths for the connections to the obtained result of division, thereby ensuring the minimum secured bandwidth for each connection and uniformly allocating the cell shaping bandwidths to the respective connections as the bandwidths freely allocable with the respective connections.
There is still further provided a source terminal according to the present invention, for transferring data cells to a destination terminal through a connection preset within an asynchronous transfer mode network including at least one transit switching system, comprising: memory means for storing therein priority information indicative of priorities for bandwidth allocation at cell transfers for each connection; and shaping bandwidth calculating means for calculating cell shaping bandwidths proportional to the priority information when a plurality of connections are simultaneously placed in a cell transfer state, whereby the shaping bandwidths are allocated to all the connections each placed in the cell transfer state.
Said shaping bandwidth calculating means may be replaced by means for multiplying a ratio obtained by dividing priority information for the respective connections by the sum of the priority information for all the connections each established over the same line and placed in the cell transfer state by the shaping bandwidth for the line, thereby calculating cell shaping bandwidths proportional to the priority information for each connection.
There is still further provided a source terminal according to the present invention, for transferring data cells to a destination terminal through a connection preset within an asynchronous transfer mode network including at least one transit switching system, comprising: means for dividing, when a plurality of connections are simultaneously placed in a cell transfer state, a shaping bandwidth for the same line as for the connections by the number of the connections each placed in the cell transfer state, of connections established over the line for transmission, thereby uniformly allocating cell shaping bandwidths to the respective connections.
When the cells cannot be transmitted in each cell shaping bandwidth calculated by the shaping bandwidth calculating means because the congestion of the network is notified by the congestion notification cell or there are no cells to be sent, bandwidth allocation calculations may be done using allocated bandwidth information with the priority information as the maximum value as an alternative to the priority information used in the shaping bandwidth calculating means.
When the cells cannot be transmitted in the cell shaping bandwidth calculated in accordance with the cell shaping bandwidth calculation due to the above-mentioned reason, the bandwidth allocation calculations may be done using allocated bandwidth information with a minimum secured bandwidth as the maximum value, as an alternative to the minimum secured bandwidth used in the allocation calculations of each cell shaping bandwidth.
According to one embodiment of the present invention, the source terminal has means for comparing in parallel shaping bandwidths obtained by performing the bandwidth allocation calculations on respective values of candidates selectable as allocated bandwidth information in parallel and shaping bandwidths calculated based on congestion notification information, thereby obtaining the optimum allocated bandwidth information.
One feature of the present invention is that each of network nodes placed in an asynchronous transfer mode network which is comprised of a source terminal, one or a plurality of transit switching systems and a destination terminal and which transfers data cells and congestion notification cells from the source terminal to the destination terminal through a pre-set connection, includes means (A) for decreasing a cell shaping bandwidth when a congestion notification cell produced by each own node is sent back with a congestion notification bit set thereto and increasing the cell shaping bandwidth when the congestion notification cell is sent back without the setting of the congestion notification bit thereto, means (B) for, when a congestion notification cell produced by another node is received, writing information indicative of a buffer congestion status of each connection related to the congestion notification cell into the congestion notification cell and sending it back to a communication path having received the congestion notification cell, and the above-described shaping bandwidth control means (C).
The above-described means (A), (B) and (C) may be provided in a line interface of the transit switching system constituting the asynchronous transfer mode network, or a trunk. Incidentally, the calculation of each cell shaping bandwidth referred to above can be done by software in the source terminal, the network nodes or the transit switching system. Further, information (priority information or the like) defined as a criterion for bandwidth allocation for each connection, which is necessary for the source terminal, the network nodes or the transit switching system, can be set from a network management device connected to the asynchronous transfer mode network.
Typical ones of various inventions of the present inventions have been shown in brief. However, the various inventions of the present application and specific configurations of these inventions will be understood from the following description.